﻿// ex6.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include "pch.h"
#include<stdio.h>
#include <iostream>
#include <time.h>
#define MAXSIZE 100 //参加排序元素的最大个数
typedef struct list
{
	int key;
}RedType;
typedef struct {
	RedType arr[MAXSIZE + 1];
	int length; //参加排序元素的实际个数
}SqList;

void print_arr(SqList s, int length)
{
	for (int i = 0; i < length; ++i)
	{
		printf("%d ", s.arr[i].key);
	}
	printf("\n");
}


void selection_sort(SqList s, int length)
{
	int i, j, m;
	int count = 0;
	int temp;	// 用于存放临时待排序的元素值

	for (i = 0; i < length - 1; i++)
	{
		m = i;
		for (j = i + 1; j < length; j++)
		{
			if (s.arr[j].key <s.arr[m].key)
				m = j;
		}
		if (m != i)
		{
			temp = s.arr[i].key;
			s.arr[i].key = s.arr[m].key;
			s.arr[m].key = temp;
			count += 3;
		}
	}
	printf("移动次数为：%d\n", count);
	print_arr(s, s.length);
}

//void insertion_sort(int array[], int length)
//{
//	int i, j;
//	int temp; 
//	for (i = 1; i < length; i++)
//	{
//		temp = array[i];
//		for (j = i - 1; (j >= 0) && (array[j] > temp); j--)
//		{
//			array[j + 1] = array[j];
//		}
//		array[j + 1] = temp;
//	}
//}

void insertion_sort(SqList s, int length)
{
	int i, j;
	int temp;
	int count = 0;
	for (i = 1; i < length; i++)
	{
		temp = s.arr[i].key;
		for (j = i - 1; (j >= 0) && (s.arr[j].key > temp); j--)
		{
			s.arr[j + 1].key = s.arr[j].key;
			count += 3;
		}
		s.arr[j + 1].key = temp;
	}
	printf("移动次数为：%d\n", count);
	print_arr(s, s.length);
}

void bubble_sort(SqList s, int length)
{
	int i, j, temp;
	int count = 0;
	for (i = 0; i < length - 1; i++) {
		for (j = 0; j < length - 1 - i; j++) {
			if (s.arr[j].key > s.arr[j + 1].key) {
				temp = s.arr[j].key;
				s.arr[j].key = s.arr[j + 1].key;
				s.arr[j + 1].key = temp;
				count += 3;
			}

		}
	}
	printf("移动次数为：%d\n", count);
	print_arr(s, s.length);
}

void shell_sort(SqList s, int length)
{
	int i;
	int j;
	int k;
	int gap;	//分组的步长
	int temp;
	int count = 0;
	for (gap = length / 2; gap > 0; gap = gap / 2)
	{
		for (i = 0; i < gap; i++) 
		{
			for (j = i + gap; j < length; j = j + gap) 
			{	//单独一次的插入排序
				if (s.arr[j].key < s.arr[j - gap].key) 
				{
					temp = s.arr[j].key;	//哨兵
					k = j - gap;
					while (k >= 0 && s.arr[k].key > temp)
					{
						s.arr[k + gap].key = s.arr[k].key;
						k = k - gap;
						count += 3;
					}
					s.arr[k + gap].key = temp;
				}
			}
		}
	}
	printf("移动次数为：%d\n", count);
	print_arr(s, s.length);
}

//
//void swap(SqList L, int i, int j)
//{
//	int temp = L.arr[i].key;
//	L.arr[i].key = L.arr[j].key;
//	L.arr[j].key = temp;
//}



int c = 0;
void quick_sort(int v[], int first, int last) 
{
	int i, s;
	void swap(int v[], int i, int j);
	if (first >= last)
		return;  //fewer than two ele
	swap(v, last, (first + last) / 2); //move partition elem
	s = first;
	for (i = first; i <= last - 1; i++)
		if (v[i] <= v[last])
		{
			swap(v, s, i);
			s += 1;
		}
	//swap(v, last, s);
	int temp;
	temp = v[s];
	v[s] = v[last];
	v[last] = temp;
	c += 3;
	quick_sort(v, first, s- 1);
	quick_sort(v, s + 1, last);
}

/*swap:interchange v[i] and v[j]*/
void swap(int v[], int i, int j) 
{
	int temp;
	temp = v[j];
	v[j] = v[i];
	v[i] = temp;
}

void percdown(int  arr[], int i, int n)
{
	int child;
	int tmp;

	for (tmp = arr[i]; 2 * i + 1 < n; i = child) {
		child = 2 * i + 1; //注意数组下标是从0开始的，所以左孩子的求发不是2*i
		if (child != n - 1 && arr[child + 1] > arr[child])
			++child;                //找到最大的儿子节点
		if (tmp < arr[child])
			arr[i] = arr[child];
		else
			break;
	}
	arr[i] = tmp;
}

void heap_sort(int arr[], int n)
{
	int i,temp;
	int count = 0;
	for (i = n / 2; i >= 0; --i)
		percdown(arr, i, n);    //构造堆
	for (i = n - 1; i > 0; --i)
	{
		//swap(&arr[0], &arr[i]);
		//	int temp;
		temp = arr[i];
		arr[i] = arr[0];
		arr[0] = temp;
		count += 3;//将最大元素（根）与数组末尾元素交换，从而删除最大元素，重新构造堆
		percdown(arr, 0, i);
	}
	printf("移动次数为：%d\n", count);
	for (i = 0; i < n; i++)
		printf("%d ", arr[i]);
}

void binaryinsert_sort(int arr[], int n)
{         
	int i, j, mid, low, high;
	int temp;
	int count = 0;
	for (i = 1; i < n; i++) 
	{
		temp = arr[i]; 
		low = 0;
		high = i;   
		while (low <= high)
		{  
			mid = (low + high) / 2; 									 
			if (temp > arr[mid])
			{             
				low = mid + 1;
			}
			else 
			{
				high = mid - 1;
			}
		}

		for (j = i - 1; j >= low; j--) 
		{ 
			arr[j + 1] = arr[j];
		}
		arr[low] = temp;
		count += 3;
	}
	printf("移动次数为：%d\n", count);
	for (i = 0; i < n; i++)
		printf("%d ", arr[i]);
}


int main()
{
	SqList A;
	int h[MAXSIZE];
	int choice;
	//int arr[10]/*用于保存10个产生的随机数*/, i;
	//int length;
	printf("请输入表的序列类别\n：1.乱序\n2.递增\n3.递减\n输入0退出\n");
	scanf_s("%d",&choice);
	printf("请输入表长：");
	scanf_s("%d",&A.length);
	switch (choice)
	{
		case 1:
		{
			srand((unsigned int)time(NULL));//设置当前时间为种子
			for (int i = 0; i < A.length; ++i)
			{
				A.arr[i].key = rand() % 100 + 1;//产生1~100的随机数
			}
			for (int i = 0; i < A.length; ++i)
			{
				h[i] = A.arr[i].key;
			}
			break;
		}
		case 2:
		{
			for (int i = 0; i < A.length; ++i)
			{
				A.arr[i].key = i;
			}
			for (int i = 0; i < A.length; ++i)
			{
				h[i] = A.arr[i].key;
			}
			break;
		}
		case 3:
		{
			for (int i = 0; i < A.length; ++i)
			{
				A.arr[i].key = A.length-i;
			}
			for (int i = 0; i < A.length; ++i)
			{
				h[i] = A.arr[i].key;
			}
			break;
		}
		case 0:
		{
			printf("程序退出！\n");
			return 0;
		}
	}
	
	print_arr(A, A.length);
	printf("\n");

	printf("简单选择排序：\n");
	selection_sort(A, A.length);
	printf("\n");

	printf("直接插入排序：\n");
	insertion_sort(A, A.length);
	printf("\n");

	printf("冒泡排序：\n");
	bubble_sort(A, A.length);
	printf("\n");

	printf("希尔排序：\n");
	shell_sort(A, A.length);
	printf("\n");

	printf("快速排序：\n");
	quick_sort(h,0,A.length);
	printf("移动次数为：%d\n",c);
	for (int i = 1; i < A.length+1; i++)
		printf("%d ", h[i]);
	printf("\n\n");

	for (int i = 0; i < A.length; ++i)//重新初始化
	{
		h[i] = A.arr[i].key;
	}
	printf("堆排序：\n");
	heap_sort(h,A.length);
	printf("\n\n");

	for (int i = 0; i < A.length; ++i)//重新初始化
	{
		h[i] = A.arr[i].key;
	}
	printf("二分插入排序：\n");
	binaryinsert_sort(h, A.length);
	printf("\n");
	system("pause");
	return 0;
}

